package Niuke;

import java.util.HashMap;
public class LRUcache {

        class Node {
            int key;
            int val;
            Node pre;
            Node next;
        }

        class DoubleList {
            Node head;
            Node tail;
        }

        DoubleList list = new DoubleList();
        HashMap<Integer, Node> data = new HashMap<>();
        int cursize = 0;
        int capacity = 0;

        public LRUcache(int capacity) {
            this.capacity = capacity;
        }

        public int get(int key) {
            if (data.containsKey(key)) {
                transfer(data.get(key));
                return data.get(key).val;
            } else
                return -1;
        }

        public void put(int key, int value) {
            if (data.containsKey(key)) {
                data.get(key).val = value;
                transfer(data.get(key));
            } else {
                if (cursize == capacity) {
                    removeLRU();
                }
                Node tmp = new Node();
                tmp.key = key;
                tmp.val = value;
                if (list.head == null) {
                    list.head = tmp;
                    list.tail = tmp;
                } else {
                    list.tail.next = tmp;
                    tmp.pre = list.tail;
                    list.tail = tmp;
                }
                data.put(key, tmp);
                cursize++;
            }
        }

        public void removeLRU() {
            int key = list.head.key;
            data.remove(key);
            list.head = list.head.next;
            if (list.head != null)
                list.head.pre = null;
            cursize--;
        }

        public void transfer(Node node) {
            if (node == list.tail)
                return;
            if (node == list.head) {
                list.head = list.head.next;
                list.head.pre = null;
                node.next = null;
                list.tail.next = node;
                node.pre = list.tail;
                list.tail = node;
                return;
            }
            node.pre.next = node.next;
            node.next.pre = node.pre;
            node.next = null;
            node.pre = null;
            list.tail.next = node;
            node.pre = list.tail;
            list.tail = node;
        }
    public static void main(String[] args) {
        LRUcache lruCache = new LRUcache(2);
        lruCache.put(1, 1);
        lruCache.put(2, 2);
        lruCache.get(1);
        lruCache.put(3, 3);
        lruCache.get(2);
        lruCache.put(4, 4);
        lruCache.get(1);
        lruCache.get(3);
        lruCache.get(4);
    }

    }

